#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
    public:
        vector<int> searchRange(int A[], int n, int target) {
            vector<int> ans;
            int lo = 0, hi = n-1;

            while (lo < hi) {
                int mid = lo + (hi-lo)/2;
                if (A[mid] >= target) hi = mid;
                else lo = mid +1; 
            }
            int low_range;
//            cout << hi << endl;
            if (A[hi] == target) low_range = hi;
            else low_range = -1;

            lo = 0, hi = n-1;

            while (lo < hi) {
                int mid = lo + (hi-lo)/2;
                if (A[mid] <= target) lo = mid+1;
                else hi = mid; 
            }
            int high_range;
    //        cout << hi << endl;
            if (A[hi] != target && A[hi-1] == target) high_range = hi-1;
            else if (A[hi] == target) high_range = hi;
            else high_range = -1;
  //          cout << low_range << " " << high_range << endl;
            ans.push_back(low_range);
            ans.push_back(high_range);
            return ans;
        }
};

//add the best code
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> ans;
        ans.push_back(-1);
        ans.push_back(-1);
        int start = -1, end = -1;
        int lo = 0, hi = n-1; 
        while(lo <= hi) {
            int mid = lo + (hi-lo)/2;
            if ((mid == 0 || A[mid-1] < A[mid]) && A[mid] == target) {
                start = mid; 
                break;
            } else if (A[mid] >= target) {
                hi = mid-1; 
            } else if (A[mid] < target) {
                lo = mid+1;
            }    
        }    
        if (start == -1) return ans; 

        lo = 0; 
        hi = n-1; 
        while(lo <= hi) {
            int mid = lo + (hi-lo)/2;
            if ((mid == n-1 || A[mid] < A[mid+1]) && A[mid] == target) {
                end = mid; 
                break;
            } else if (A[mid] > target) {
                hi = mid-1;
            } else if (A[mid] <= target) {
                lo = mid+1;
            }    
        }    

        if (end == -1) return ans; 
        ans[0] = start;
        ans[1] = end;     
        return ans; 
    }   


//test in 1337 online judge and pass all the test`
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    int test[] = {5, 7, 7, 8, 8, 10};
    mySolution.searchRange(test, sizeof(test)/sizeof(int), 8); 

    cout << "-----------------Test 2--------------------" << endl;
    int test1[] = {2,2,2};
    mySolution.searchRange(test1, sizeof(test1)/sizeof(int), 2); 


    cout << "-----------------Test 3--------------------" << endl;
    int test2[] = {2};
    mySolution.searchRange(test2, sizeof(test2)/sizeof(int), 2); 


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
